De Morgan's Laws (Set Theory)

De Morgan's Laws are a pair of algebraic laws for the complement of the union or intersection of any number of sets.

Theorem

For any collection of sets \(\{A_{i}\}_{i \in I}\):

\[ \left(\bigcup_{i \in I} A_{i}\right)^{c} = \bigcap_{i \in I} A_{i}^{c} \quad \text{and} \quad \left(\bigcap_{i \in I} A_{i}\right)^{c} = \bigcup_{i \in I} A_{i}^{c}.\]

In the case of a pair of sets these laws reduce to:

\[ (A \cup B)^{c} = A^{c} \cap B^{c} \quad \text{and} \quad (A \cap B)^{c} = A^{c} \cup B^{c}.\]

Proof

The proofs for De Morgan's are quite simple, here is a proof for the first one:

\[\begin{align*} & x \in \left(\bigcup_{i \in I} A_{i}\right)^{c} \\ \iff & x \not \in \bigcup_{i \in I} A_{i} \\ \iff & x \not \in A_{i} \quad \forall i \in I \\ \iff & x \in A_{i}^{c} \quad \forall i \in I \\ \iff & x \in \bigcap_{i \in I} A_{i}^{c} \\ \end{align*}\]

and the second follows either by letting \(B_{i} = A_{i}^{c}\) and taking the complement of both sides:

\[\begin{align*} & \left(\bigcup_{i \in I} A_{i}\right)^{c} = \bigcap_{i \in I} A_{i}^{c} \\ \implies & \bigcup_{i \in I} A_{i} = \left(\bigcap_{i \in I} A_{i}^{c}\right)^{c} \\ \implies & \bigcup_{i \in I} B_{i}^{c} = \left(\bigcap_{i \in I} B_{i}\right)^{c} \\ \end{align*}\]

or directly with a very similar method to the first.

Relationship to Logic

Here is a proof for one of De Morgan's Laws for sets in the special case with only two sets, which depends on the "equivalent" law for logic, in the interest of showing why there is a close relationship between these ideas. Specifically, this correspondence comes from the facts that:

\[\begin{align*} &x \in A^{c} \iff \lnot (x \in A) \\ &x \in (A \cup B) \iff x \in A \lor x \in B \\ &x \in (A \cap B) \iff x \in A \land x \in B \end{align*}\]

Here is the proof:

\[\begin{align*} (A \cup B)^{c} &= \{x \in U \ | \ x \notin (A \cup B)\} \\ &= \{x \in U \ | \ \lnot(x \in (A \cup B))\} \\ &= \{x \in U \ | \ \lnot(x \in A \lor x \in B))\} \\ &= \{x \in U \ | \ \lnot (x \in A) \land \lnot (x \in B))\} \\ &= \{x \in U \ | \ (x \notin A) \land (x \notin B))\} \\ &= \{x \in U \ | \ (x \in A^{c}) \land (x \in B^{c}))\} \\ &= \{x \in U \ | \ x \in (A^{c} \cap B^{c})\} \\ \end{align*}\]